package Alibaba;

import common.ListNode;

/**
 * @author zhangmin
 * @create 2022-01-31 13:09
 * 92. 反转链表 II
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */
public class reverseBetween92 {
    //翻转从head开始的n个节点
    ListNode successor=null;
    ListNode reverseN(ListNode head,int n){
        if (n==1){
            //找到了第n+1个节点作为最后的后序节点
            successor=head.next;
            return head;
        }
        ListNode next = reverseN(head.next, n - 1);
        head.next.next=head;
        head.next=successor;
        return next;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left==1){
            return reverseN(head,right);
        }
        head.next=reverseBetween(head.next,left-1,right-1);
        return head;
    }
}
